超ド文系出身　アルゴリズム攻略法

#基本情報技術者試験

松浦

2023.06.02

この記事は公開されてから1年以上経過しています。情報が古い可能性がありますので、ご注意ください。

先日、新制度になった基本情報技術者試験を受験してきました。ほとんどの人がつまづくという『アルゴリズム』。私なりに気を付けていたことをご紹介したいと思います。

アルゴリズムとは

アルゴリズムとは、ある目的を達成するための「作業手順」のことです。特定の目的を達成したりするための計算手順や処理手順であり、その手順に沿っていれば、誰がやっても同じ答え（結果）を出せるのがアルゴリズムの特徴です。プログラミングの世界で使われることが多い印象ですね。

さて、このアルゴリズム。初めて私が目にしたのは基本情報技術者試験の勉強をはじめたときでした。これは平成21年秋期の旧午後試験の問題（一部抜粋）です。

・・・初めて見た時、本気でムスカになりました。目がつぶれるかと思うほどめまいが・・・（笑）

こちらをご覧ください。

これはまだ基本情報技術者試験が『第二種情報処理技術者試験』と呼ばれていた頃のアルゴリズム問題です。先ほどの問題と比べてどうでしょうか？

漢字が多く、日本語注釈も多いですよね。前者のは、初見では何がなんだかさっぱりわかりませんが、後者のは「国語」や「成績表」という言葉があるので、なんらかの成績表の処理をしているのかなーぐらいの想像がつきます。（プログラム名に「成績表作成」ってありますし笑）このままこんな問題を出し続けてくれていれば、私も苦労しなかったかもしれないですが、年々、プログラミング的思考を身に着けてほしいというIPAの強い願いから、徐々にプログラミングに沿った疑似言語で問いてくるようになりました。

アルゴリズム攻略　心得

旧午後試験の時はアルゴリズムは必須問題で２５％のウェイトを占めていました。でも「他の選択問題を完璧におさえ、アルゴリズムは捨てる」という手法も大変トリッキーではありつつもできなくはなかったわけです。ところが新制度になり、B試験は全問題回答必須、そして問題のアルゴリズムが８０％を占めるという、どう考えても無視できない種目になりました。

私は超ド文系出身です。最初の頃は手も足も出ませんでした。どの本を読んでも、動画を見ても理解ができないのです。それでも少しずつ、少しずつ解けるようになってきたので、その方法をご紹介したいと思います。

１．必ずトレースする

トレースは筆算に似ています。例えば123×456という桁数の多い計算では、各行の計算結果や繰り上がりの数字を覚えていられません。急がば回れ。時間がない！と手を動かさず頭の中で考えてばかりだと余計に時間がかかります。地道にトレースしていくことをお勧めします。

私はまずはトレースができるようになることから練習しました。初心者の方は、いきなり最初にお見せしたようなアルゴリズムでトレースしようとしても難しいと思います。いい練習材料としては、A問題で出てくるような単純なアルゴリズムでトレースしてみるといいと思います。

２．処理結果を予測する

問題によっては、具体的な数値などを提示しないものもあります。その場合は、どのような処理をするプログラムなのかを読み、自分で簡単な数字をあてはめて処理結果を予測するとスムーズに解けます。

上記のような問題があった場合、例えば bはsumを何で割ったらよいのかという具体的な数値が分かりません。問題を読むと「平均を戻り値として返す」＝ようするに平均を求めるプログラムであると分かります。

私の場合、あんまり要素数が多くても計算が面倒なため要素数は３つにし、中身は「１，３，５」で平均は「３」として計算しました。このように、何でもよいので処理結果を自分の計算しやすい数値にあてはめ、トレースするのがよいでしょう。

３．要素番号の開始が０なのか１なのか

だいたいどの問題も「要素番号は０から始まる」「１から始まる」といった文言があります。

ここを見逃してしまうと、のちの計算がすべてくるうことになりますので注意が必要です。必ず要素番号の開始は０なのか１なのか、確認しましょう。

４．iなのか、[i]なのか

私が最後の最後までよく間違え、ひっかかっていた部分です。これを間違うと、３．の要素番号と同じですべての計算がくるってしまいます。

①３．の話に戻りますが、このプログラムでは「要素番号は１」から始まります。

②手続qsortをqsort(1, 5)と呼び出しているので、leftには「１」が、rightには「５」が入ります。

③ただしdata [right] は「５」ではありません。配列の[right]番目という意味なので、③を見ると５番目は「３」です。これが注意すべきところです。この[ ]に気づかずにそのまま「５」をあてはめてしまうと以降の計算が全て狂います。

④も同じくdata[i]は「１」ではありません。配列の[i]番目という意味なので、③を見ると１番目は「２」が入っています。

この注意ポイントは参考書の最初のページにだいたい書いてあるのですが、各問題の解説には載っていない（というか、ここまで丁寧に書いていない）ため、私はしばらくこれに気づけず、解説を理解できずずーっと悩んでいました。単純なことなのですが、とても重要なことであり、繰り返しになりますがここを間違えるとすべての計算が狂うので注意が必要です。